Social network platforms have information on aspects of their members' social lives. People's relationships is one primary kind of such information. Therefore, relationship mining on social networks is becoming a promising research direction, but previously it has dealt only with explicit relations, i.e., one has background knowledge to follow in addition to the data while uncovering the target relationship. For example, people can discover advisor-advisee relation in an academic collaboration network using the background knowledge of the properties of publication and collaboration records. However, in many practical cases, there are no such explicit clues. The relations are latent when there is little or no background knowledge. For example, on a professional social network service, managers may have connections with their employees. Although this manager-employee relation exists on the network, inferring it is an extremely challenging task. Due to its latent nature, usually none of the features like connections, job titles, working experiences, and the like, explicitly indicates working relations directly. Furthermore, the relation can be hierarchical. However, from pairwise manager-employee relations on a professional social network, the organization structure of a company may be able to be inferred. For example, the latent social relationship may be inferred and used to a construct a hierarchy from heterogeneous data sources. Since the relation is latent, there is appears to be no single source or straightforward combination of sources of data that contain explicit clues of it. Concepts in the physics domain such as the effect of gravitational force on escape velocity may be used to design a force-based schema to integrate the information from heterogeneous sources on social networks harmonically to predict the pairwise latent relations. The hierarchy construction may be modelled with a Reduced Markov Decision Process, which utilizes pair-wise relations. This may be achieved by relationship mining on an online social network service.
Generally speaking, online social network services provide users with a mechanism for defining, and memorializing in a digital format, their relationships with other people. This digital representation of real-world relationships is frequently referred to as a social graph. Many social network services utilize a social graph to facilitate electronic communications and the sharing of information between its users or members. For instance, the relationship between two members of a social network service, as defined in the social graph of the social network service, may determine the access and sharing privileges that exist between the two members. As such, the social graph in use by a social network service may determine the manner in which two members of the social network service can interact with one another via the various communication and sharing mechanisms supported by the social network service.
Some social network services aim to enable friends and family to communicate and share with one another, while others are specifically directed to business users with a goal of facilitating the establishment of professional networks and the sharing of business information. For purposes of the present disclosure, the terms “social network” and “social network service” are used in a broad sense and are meant to encompass services aimed at connecting friends and family (often referred to simply as “social networks”), as well as services that are specifically directed to enabling business people to connect and share business information (also commonly referred to as “social networks” but sometimes referred to as “business networks” or “professional networks”).
With many social network services, members are prompted to provide a variety of personal information, which may be displayed in a member's personal web page. Such information is commonly referred to as “personal profile information”, or simply “profile information”, and when shown collectively, it is commonly referred to as a member's profile. For example, with some of the many social network services in use today, the personal information that is commonly requested and displayed as part of a member's profile includes a member's age (e.g., birth date), gender, contact information, home town, address, the name of the member's spouse and/or family members, a photograph of the member, interests, and so forth. With certain social network services, such as some business network services, a member's personal information may include information commonly included in a professional resume or curriculum vitae, such as information about a person's education, employment history, job skills, professional organizations, and so forth. With some social network services, a member's profile may be viewable to the public by default, or alternatively, the member may specify that only some portion of the profile is to be public by default. As such, many social network services serve as a sort of directory of people to be searched and browsed.
Because social network services are a rich source of information about people, social network services are an extremely useful tool when performing certain tasks. For example, many people use social network services to search for, and/or browse, member profiles that exhibit various desired characteristics. For instance, a person may search for persons who have profiles indicating the possession of certain technical skills, and educational and professional experiences and backgrounds. Similarly, when someone needs to hire a person employed in a particular profession (e.g., a general contractor, a doctor, a lawyer, a landscaper, a plumber, an investment banker, and so forth), that person may turn to a social network service to identify persons who possess the requisite skills and qualifications. In another scenario, a person may desire to contact someone for the purpose of exploring or proposing the possibility of a particular business arrangement or relationship. Accordingly, the person may use a social network service to identify the appropriate persons to contact. Additionally, as discussed subsequently, pairwise manager-employee relations may be determined on a social network, and from this the organization structure of a company may be able to be inferred.